import sortedcontainers


class Solution(object):
    def jobScheduling(self, startTime, endTime, profit):
        d = sortedcontainers.SortedDict()
        n = len(startTime)
        st = [[startTime[i], endTime[i], profit[i]] for i in range(n)]
        st.sort(key=lambda x: x[1])
        for s, e, p in st:
            s_index = d.bisect_right(s)
            s_value = 0
            if s_index > 0:
                s_value = d.peekitem(s_index - 1)[1]
            e_index = d.bisect_right(e)
            if e_index > 0:
                if s_value + p > d.peekitem(e_index - 1)[1]:
                    d[e] = max(d.setdefault(e, 0), s_value + p)
            else:
                d[e] = max(d.setdefault(e, 0), s_value + p)
        return max(list(d.values()))


data = Solution()
startTime = [1, 2, 3, 3]
endTime = [3, 4, 5, 6]
profit = [50, 10, 40, 70]
print(data.jobScheduling(startTime, endTime, profit))
